%% Copyright (C) 2013 
%% 
%% This program is free software; you can redistribute it and/or modify
%% it under the terms of the GNU General Public License as published by
%% the Free Software Foundation; either version 2 of the License, or
%% (at your option) any later version.
%% 
%% This program is distributed in the hope that it will be useful,
%% but WITHOUT ANY WARRANTY; without even the implied warranty of
%% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%% GNU General Public License for more details.
%% 
%% You should have received a copy of the GNU General Public License
%% along with Octave; see the file COPYING.  If not, see
%% <http://www.gnu.org/licenses/>.

%% [ CaminhoFormiga ] = Heu2OPT (CaminhoFormiga, MatDistancia, combinacoes, cidades)
%% CaminhoFormiga pode ser uma estrututa com objetos:
%%	.caminho e 
%%	.comprimento
%% ou um vetor de caminho.
%% combinacoes é uma matriz (N linhas X 2 colunas) gerada pela função combnk,
%% onde cada linha é uma combinacao de 2 elementos.
%% cidades é uma matriz (N X 3) sendo coluna 1 2 e 3 = (indice, x, y)


function [ CaminhoFormiga ] = Heu2OPT_desfaz_cruz (CaminhoFormiga, MatDistancia, combinacoes, cidades)
	
	N = length(cidades);
	
	if(isstruct(CaminhoFormiga))
		SeqCidades = CaminhoFormiga.caminho(1:N);
		comprimentoatual = CaminhoFormiga.comprimento;
	else
		SeqCidades = CaminhoFormiga(1:N);
	end%if
	
	% Procura UM cruzamento, entre todas as arestas existentes
	for combinacaoAtual = 1:length(combinacoes)
	  v1Aresta1 = combinacoes(combinacaoAtual, 1);
	  v1Aresta2 = combinacoes(combinacaoAtual, 2);
	  
	  v2Aresta1 = v1Aresta1+1;
	  v2Aresta2 = v1Aresta2+1;
	  
	  % Aqui, '2' é X; '3' é Y.
	  XAresta1 = [cidades(SeqCidades(v1Aresta1), 2) , cidades(SeqCidades(v2Aresta1), 2)];
	  YAresta1 = [cidades(SeqCidades(v1Aresta1), 3) , cidades(SeqCidades(v2Aresta1), 3)];

	  XAresta2 = [cidades(SeqCidades(v1Aresta2), 2) , cidades(SeqCidades(v2Aresta2), 2)];
	  YAresta2 = [cidades(SeqCidades(v1Aresta2), 3) , cidades(SeqCidades(v2Aresta2), 3)];
	  
	  [Xcruzam, Ycruzam] = intersections( [XAresta1],[YAresta1] , [XAresta2],[YAresta2] );
	  
	  % se há cruzamento, aplica 2-opt
	  if( (isempty(Xcruzam) == false) && (isempty(Ycruzam) == false) )
	    
	    j2 = SeqCidades(v2Aresta1);
	    k2 = SeqCidades(v2Aresta2);
	    SeqCidades(v2Aresta1) = k2;
	    SeqCidades(v2Aresta2) = j2;
	    
	    break;
	  end
	  
	end%for
	
	SeqCidades(end+1) = SeqCidades(1);
	
	comprimentonovo = calcula_comprimento(N, SeqCidades, MatDistancia);
	
	if(isstruct(CaminhoFormiga))
	  CaminhoFormiga.comprimento = comprimentonovo;
	  CaminhoFormiga.caminho = SeqCidades;
	else
	  CaminhoFormiga = SeqCidades;
	end%if
	
end%function

